{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Number of Swaps to Make the String Balanced"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #greedy #two-pointers #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #贪心 #双指针 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minSwaps"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #使字符串平衡的最小交换次数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个字符串 <code>s</code> ，<strong>下标从 0 开始</strong> ，且长度为偶数 <code>n</code> 。字符串 <strong>恰好</strong> 由 <code>n / 2</code> 个开括号 <code>'['</code> 和 <code>n / 2</code> 个闭括号 <code>']'</code> 组成。</p>\n",
    "\n",
    "<p>只有能满足下述所有条件的字符串才能称为 <strong>平衡字符串</strong> ：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>字符串是一个空字符串，或者</li>\n",
    "\t<li>字符串可以记作 <code>AB</code> ，其中 <code>A</code> 和 <code>B</code> 都是 <strong>平衡字符串</strong> ，或者</li>\n",
    "\t<li>字符串可以写成 <code>[C]</code> ，其中 <code>C</code> 是一个 <strong>平衡字符串</strong> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>你可以交换 <strong>任意</strong> 两个下标所对应的括号 <strong>任意</strong> 次数。</p>\n",
    "\n",
    "<p>返回使<em> </em><code>s</code> 变成 <strong>平衡字符串</strong> 所需要的 <strong>最小</strong> 交换次数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"][][\"\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>交换下标 0 和下标 3 对应的括号，可以使字符串变成平衡字符串。\n",
    "最终字符串变成 \"[[]]\" 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"]]][[[\"\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>执行下述操作可以使字符串变成平衡字符串：\n",
    "- 交换下标 0 和下标 4 对应的括号，s = \"[]][][\" 。\n",
    "- 交换下标 1 和下标 5 对应的括号，s = \"[[][]]\" 。\n",
    "最终字符串变成 \"[[][]]\" 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"[]\"\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>这个字符串已经是平衡字符串。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == s.length</code></li>\n",
    "\t<li><code>2 &lt;= n &lt;= 10<sup>6</sup></code></li>\n",
    "\t<li><code>n</code> 为偶数</li>\n",
    "\t<li><code>s[i]</code> 为<code>'['</code> 或 <code>']'</code></li>\n",
    "\t<li>开括号 <code>'['</code> 的数目为 <code>n / 2</code> ，闭括号 <code>']'</code> 的数目也是 <code>n / 2</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-number-of-swaps-to-make-the-string-balanced](https://leetcode.cn/problems/minimum-number-of-swaps-to-make-the-string-balanced/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-number-of-swaps-to-make-the-string-balanced](https://leetcode.cn/problems/minimum-number-of-swaps-to-make-the-string-balanced/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"][][\"', '\"]]][[[\"', '\"[]\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        a = s.count('1')\n",
    "        b = n - a\n",
    "        if abs(a - b) > 1:\n",
    "            return -1\n",
    "        \n",
    "        def f(x):\n",
    "            res = 0\n",
    "            for ch in s:\n",
    "                if int(ch) != x:\n",
    "                    res += 1\n",
    "                x ^= 1\n",
    "            return res\n",
    "\n",
    "        if a == b:\n",
    "            return min(f(1), f(0)) // 2\n",
    "        elif a > b:\n",
    "            return f(1) // 2\n",
    "        else:\n",
    "            return f(0) // 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        counter = Counter(c for c in s)\n",
    "        if abs(counter['0'] - counter['1']) > 1: return -1\n",
    "        # 默认 0 开头，否则 n  - needSwap\n",
    "        exp = 1\n",
    "        cnt = 0\n",
    "        for c in s:\n",
    "            if int(c) == exp: cnt += 1\n",
    "            exp = 1 - exp\n",
    "        \n",
    "        a, b = cnt, n - cnt\n",
    "        if a % 2 == 1 and b % 2 == 1: return -1\n",
    "        if a % 2 == 0 and b % 2 == 0: return min(a, b) // 2\n",
    "        return a // 2 if a % 2 == 0 else b // 2\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        zeros = 0\n",
    "        ones = 0\n",
    "        for c in s:\n",
    "            if(c == '0'):\n",
    "                zeros += 1\n",
    "            else:\n",
    "                ones += 1\n",
    "        if(abs(zeros-ones) > 1):\n",
    "            return -1\n",
    "        result = 0\n",
    "        if(zeros > ones):\n",
    "            for i in range(len(s)):\n",
    "                if(s[i] == '1' and i % 2 == 0):\n",
    "                    result += 1\n",
    "        elif(zeros < ones):\n",
    "            for i in range(len(s)):\n",
    "                if(s[i] == '1' and i % 2 == 1):\n",
    "                    result += 1\n",
    "        else:\n",
    "            res1 = 0\n",
    "            for i in range(len(s)):\n",
    "                if(s[i] == '1' and i % 2 == 1):\n",
    "                    res1 += 1\n",
    "            res2 = 0\n",
    "            for i in range(len(s)):\n",
    "                if(s[i] == '1' and i % 2 == 0):\n",
    "                    res2 += 1\n",
    "            result = min(res1, res2)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        cnt1 = s.count('1')\n",
    "        cnt2 = len(s) - cnt1\n",
    "        if abs(cnt1 - cnt2) > 1:\n",
    "            return -1\n",
    "\n",
    "        cnt = [0, 0]    # 第一位表示开头为1时不同的数量，第二位表示开头为0时不同的数量\n",
    "        for i, c in enumerate(s):\n",
    "            # 偶数为1，给1加，偶数为0，给0加。奇数为1，给0加，奇数为0，给1加\n",
    "            cnt[i & 1 ^ int(c)] += 1\n",
    "        if cnt1 > cnt2:\n",
    "            return cnt[0] + 1 >> 1\n",
    "        elif cnt1 == cnt2:\n",
    "            return min(cnt) + 1 >> 1\n",
    "        return cnt[1] + 1 >> 1\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        cnt= Counter(s)\n",
    "        if abs(cnt[\"0\"]-cnt[\"1\"]) > 1:\n",
    "            return -1\n",
    "        m = n//2\n",
    "        rest = n-2*m\n",
    "        ans = inf\n",
    "        for t in [\"01\"*m+\"0\"*rest, \"10\"*m+\"1\"*rest]:\n",
    "            if Counter(t) == cnt:\n",
    "                cur = sum(s[i]!=t[i] for i in range(n))\n",
    "                if cur //2 <ans:\n",
    "                    ans = cur//2\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        a = s.count(\"0\")\n",
    "        b = n-a\n",
    "        if abs(a-b)>1:return -1\n",
    "        if a>b:\n",
    "            temp = 0\n",
    "            # 0比1多\n",
    "            for i in range(0,n,2):\n",
    "                if s[i] != \"0\":\n",
    "                    temp+=1\n",
    "            return temp\n",
    "        elif b>a:\n",
    "            temp = 0\n",
    "            for i in range(0,n,2):\n",
    "                if s[i]!=\"1\":\n",
    "                    temp+=1\n",
    "            return temp\n",
    "        else:\n",
    "            temp = 0\n",
    "            for i in range(0,n,2):\n",
    "                if s[i]=='0':\n",
    "                    temp+=1\n",
    "            return min(temp,n//2-temp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        ans = 0x3f3f3f3f\n",
    "        n = len(s)\n",
    "        num_zeros = s.count('0')\n",
    "        num_ones  = n - num_zeros\n",
    "        if abs(num_ones - num_zeros) > 1:\n",
    "            return -1\n",
    "        target = 0        \n",
    "        cnt = 0\n",
    "        for c in s:\n",
    "            if int(c) != target: cnt += 1\n",
    "            target = 1 - target\n",
    "        if cnt % 2 == 0:\n",
    "            ans = min(ans, cnt // 2)\n",
    "        cnt = 0\n",
    "        target = 1\n",
    "        for c in s:\n",
    "            if int(c) != target: cnt += 1\n",
    "            target = 1 - target       \n",
    "        if cnt % 2 == 0:\n",
    "            ans = min(ans, cnt // 2)\n",
    "        return ans\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    \"\"\"\r\n",
    "        只有兩種情況: 010101... or 101010...\r\n",
    "        分別計算兩種情況的交換次數, 取最小值\r\n",
    "    \"\"\"\r\n",
    "    def minSwaps(self, s: str) -> int:\r\n",
    "        n = len(s)\r\n",
    "        cnt0_0 = cnt0_1 = 0 # 010101... 0->1, 1->0\r\n",
    "        cnt1_0 = cnt1_1 = 0 # 101010... 0->1, 1->0\r\n",
    "        for idx, ch in enumerate(s):\r\n",
    "            if idx % 2 == 0:\r\n",
    "                if ch == '0':\r\n",
    "                    cnt1_0 += 1 # '1'01010... 0->1\r\n",
    "                else:\r\n",
    "                    cnt0_1 += 1 # '0'10101... 1->0\r\n",
    "            else:\r\n",
    "                if ch == '0':\r\n",
    "                    cnt0_0 += 1 # 0'1'0101... 0->1\r\n",
    "                else:\r\n",
    "                    cnt1_1 += 1 # 1'0'1010... 1->0\r\n",
    "        if cnt0_0 == cnt0_1 and cnt1_0 == cnt1_1:\r\n",
    "            return min(cnt0_0, cnt1_0)\r\n",
    "        elif cnt0_0 == cnt0_1:\r\n",
    "            return cnt0_0\r\n",
    "        elif cnt1_0 == cnt1_1:\r\n",
    "            return cnt1_0\r\n",
    "        else:\r\n",
    "            return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        ones, zeros = 0, 0\n",
    "        odd = [0] * 2 \n",
    "        for i in range(n):\n",
    "            ones += int(s[i] == '1')\n",
    "            zeros += int(s[i] == '0')\n",
    "            if i % 2 == 0:\n",
    "                odd[0] += int(s[i] == '0')\n",
    "                odd[1] += int(s[i] == '1')\n",
    "            \n",
    "        if abs(ones- zeros) > 1:\n",
    "            return -1 \n",
    "        if n % 2 == 0:\n",
    "            return min(odd[0], odd[1]) \n",
    "        elif ones > zeros:\n",
    "            return odd[0] \n",
    "        else:\n",
    "            return odd[1] \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        count0, count1 = 0, 0\n",
    "        for c in s:\n",
    "            if c == '1':\n",
    "                count1 += 1\n",
    "            else:\n",
    "                count0 += 1\n",
    "        \n",
    "        if abs(count0 - count1) > 1:\n",
    "            return -1\n",
    "        \n",
    "        res = len(s)\n",
    "        res1 = 0\n",
    "        if count0 >= count1:\n",
    "            for i in range(0, len(s), 2):\n",
    "                if s[i] != '0':\n",
    "                    res1 += 1\n",
    "            res = min(res, res1)\n",
    "        res2 = 0\n",
    "        if count1 >= count0:\n",
    "            for i in range(0, len(s), 2):\n",
    "                if s[i] != '1':\n",
    "                    res2 += 1\n",
    "            res = min(res, res2)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        cnt = [0, 0]    # 第一位表示开头为1时不同的数量，第二位表示开头为0时不同的数量\n",
    "        c1 = 0\n",
    "        for i, c in enumerate(s):\n",
    "            # 偶数为1，给1加，偶数为0，给0加。奇数为1，给0加，奇数为0，给1加\n",
    "            cnt[i & 1 ^ int(c)] += 1\n",
    "            if c == '1':\n",
    "                c1 += 1\n",
    "\n",
    "        c0 = len(s) - c1\n",
    "        if abs(c1 - c0) > 1:\n",
    "            return -1\n",
    "        if c1 > c0:\n",
    "            diff = cnt[0]\n",
    "        elif c1 == c0:\n",
    "            diff = min(cnt)\n",
    "        else:\n",
    "            diff = cnt[1]\n",
    "        return diff + 1 >> 1\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        slen = len(s)\n",
    "        s1 = slen//2\n",
    "        s1_n = 0\n",
    "        s0_n = 0\n",
    "        n1 = 0\n",
    "        for i in range(slen):\n",
    "            if s[i] == \"1\":\n",
    "                n1+=1\n",
    "        if slen%2 == 1:\n",
    "            if n1 > slen//2+1 or n1 < slen//2:\n",
    "                return -1\n",
    "        else:\n",
    "            if n1 != slen//2:\n",
    "                return -1\n",
    "        #由1开始进行遍历\n",
    "        flag = True\n",
    "        for i in range(slen):\n",
    "            if flag:\n",
    "                if s[i] != \"1\":\n",
    "                    s1_n+=1\n",
    "                flag = False\n",
    "            else:\n",
    "                if s[i] != \"0\":\n",
    "                    s1_n+=1\n",
    "                flag = True\n",
    "        \n",
    "        flag = False\n",
    "        for i in range(slen):\n",
    "            if flag:\n",
    "                if s[i] != \"1\":\n",
    "                    s0_n+=1\n",
    "                flag = False\n",
    "            else:\n",
    "                if s[i] != \"0\":\n",
    "                    s0_n+=1\n",
    "                flag = True\n",
    "\n",
    "        if s1_n%2 == 1 and s0_n%2 == 1:\n",
    "            return -1\n",
    "        if s1_n%2 == 1 and s0_n%2 == 0:\n",
    "            return s0_n//2                    \n",
    "        if s1_n%2 == 0 and s0_n%2 == 1:\n",
    "            return s1_n//2\n",
    "        return s1_n//2 if s1_n//2<s0_n//2 else s0_n//2      "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        cnt1 = s.count('1')\n",
    "        cnt2 = len(s) - cnt1\n",
    "        if abs(cnt1 - cnt2) > 1:\n",
    "            return -1\n",
    "\n",
    "        cnt = [0, 0]    # 第一位表示开头为1时不同的数量，第二位表示开头为0时不同的数量\n",
    "        for i, c in enumerate(s):\n",
    "            # 偶数为1，给1加，偶数为0，给0加。奇数为1，给0加，奇数为0，给1加\n",
    "            cnt[i & 1 ^ int(c)] += 1\n",
    "\n",
    "        if cnt1 > cnt2:\n",
    "            diff = cnt[0]\n",
    "        elif cnt1 == cnt2:\n",
    "            diff = min(cnt)\n",
    "        else:\n",
    "            diff = cnt[1]\n",
    "        return diff + 1 >> 1\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        c0 = c1 = a = b = 0\n",
    "        for i, c in enumerate(s):\n",
    "            c0 += c == '0'\n",
    "            c1 += c == '1'\n",
    "            a += i & 1 == 0 and c != '0'\n",
    "            b += i & 1 == 0 and c != '1'\n",
    "        # 不存在解\n",
    "        if abs(c0 - c1) > 1: return -1\n",
    "        return min(a, b) if c0 == c1 else (a if c0 > c1 else b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "      cnt = 0\n",
    "      first = s[0]\n",
    "      n = len(s)\n",
    "      ans1 = 0\n",
    "      ans2 = 0\n",
    "      for i in range(0, n):\n",
    "        if s[i] == first:\n",
    "          cnt += 1\n",
    "        else:\n",
    "          cnt -= 1\n",
    "        if i % 2 == 0 and s[i] != first:\n",
    "          # print(i)\n",
    "          ans1 += 1\n",
    "        if i % 2 == 0 and s[i] == first:\n",
    "          ans2 += 1\n",
    "      ans = ans1 if cnt > 0 else ans2\n",
    "      if cnt == 0:\n",
    "        ans = min(ans1, ans2)\n",
    "      if abs(cnt) > 1:\n",
    "        ans = -1\n",
    "      return  ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        # 统计0，1个数\n",
    "        zeros, ones = s.count('0'), s.count('1')\n",
    "        # 无法满足要求的情况\n",
    "        if (zeros - ones) > 1 or (ones - zeros) > 1:\n",
    "            return -1\n",
    "        n = len(s)\n",
    "        # 已经达到要求的情况\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        res1, res2 = float(inf), float(inf)\n",
    "        # 0101\n",
    "        if zeros >= ones:\n",
    "            tmp = '0b'\n",
    "            tmp += '01' * ones\n",
    "            tmp += '0'\n",
    "            a = int(s, 2)\n",
    "            b = int(tmp, 2)\n",
    "            c = str(bin(a ^ b))\n",
    "            res1 = c.count('1') // 2            \n",
    "        # 1010\n",
    "        if ones >= zeros:\n",
    "            res2 = 0\n",
    "            tmp = '0b'\n",
    "            tmp += '10' * zeros\n",
    "            tmp += '1'\n",
    "            a = int(s, 2)\n",
    "            b = int(tmp, 2)\n",
    "            c = str(bin(a ^ b))\n",
    "            res2 = c.count('1') // 2\n",
    "            \n",
    "        return min(res1, res2)\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        c0, c1 = s.count(\"0\"), s.count(\"1\")\n",
    "        if c0 + 1 < c1:\n",
    "            return -1\n",
    "        elif c0 + 1 == c1:\n",
    "            ans = 0\n",
    "            for i in range(0, len(s), 2):\n",
    "                if s[i] != \"1\":\n",
    "                    ans += 1\n",
    "            return ans\n",
    "        elif c0 == c1:\n",
    "            ans1 = 0\n",
    "            for i in range(0, len(s), 2):\n",
    "                if s[i] == \"0\":\n",
    "                    ans1 += 1\n",
    "            ans2 = len(s) // 2 - ans1\n",
    "            return min(ans1, ans2)\n",
    "        elif c0 == c1 + 1:\n",
    "            ans = 0\n",
    "            for i in range(0, len(s), 2):\n",
    "                if s[i] != \"0\":\n",
    "                    ans += 1\n",
    "            return ans\n",
    "        else:  # c0 > c1 + 1\n",
    "            return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        ans = inf\n",
    "        c0 = c1 = 0\n",
    "        for i, x in enumerate(s):\n",
    "            if i % 2 and x == '0':\n",
    "                c0 += 1\n",
    "            if i % 2 == 0 and x == '1':\n",
    "                c1 += 1\n",
    "        if c0 == c1:\n",
    "            ans = min(ans, c0)\n",
    "        c0 = c1 = 0\n",
    "        for i, x in enumerate(s):\n",
    "            if i % 2 and x == '1':\n",
    "                c0 += 1\n",
    "            if i % 2 == 0 and x == '0':\n",
    "                c1 += 1\n",
    "        if c0 == c1:\n",
    "            ans = min(ans, c0)            \n",
    "        return ans if ans < inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        cnt0, cnt1 = s.count('0'), s.count('1')\n",
    "        n = len(s)\n",
    "        if not ((n % 2 and abs(cnt0 - cnt1) == 1) or (n % 2 == 0 and cnt0 == cnt1)):\n",
    "            return -1 \n",
    "        \n",
    "        if n % 2 == 0:\n",
    "            t1 = '01' * (n // 2)\n",
    "            t2 = '10' * (n // 2)\n",
    "        else:\n",
    "            t1 = '01' * (n // 2) + '0'\n",
    "            t2 = '10' * (n // 2) + '1'\n",
    "        ans = n\n",
    "        c1 = sum(a != b for a, b in zip(s, t1))\n",
    "        if c1 % 2 == 0: ans = min(ans, c1 // 2)\n",
    "        c2 = sum(a != b for a, b in zip(s, t2))\n",
    "        if c2 % 2 == 0: ans = min(ans, c2 // 2)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        sum_,cnt1,cnt2 = 0,0,0\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == '0':\n",
    "                sum_ += 1\n",
    "            if i%2==0:\n",
    "                if s[i] == '1':\n",
    "                    cnt1 += 1\n",
    "                else:\n",
    "                    cnt2 += 1\n",
    "            else:\n",
    "                if s[i] == '0':\n",
    "                    cnt1 += 1\n",
    "                else:\n",
    "                    cnt2 += 1\n",
    "        if abs(2*sum_ - len(s)) > 1:\n",
    "            return -1\n",
    "        else:\n",
    "            res = len(s)//2\n",
    "            if cnt1%2 == 0:\n",
    "                res = min(res,cnt1//2)\n",
    "            if cnt2%2 == 0:\n",
    "                res = min(res,cnt2//2)\n",
    "            return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        c1 = s.count('1')\n",
    "        c2 = n - c1\n",
    "        if abs(c1-c2) > 1:\n",
    "            return -1\n",
    "        if c1 == c2:\n",
    "            return min(s[::2].count('0'), s[1::2].count('0'))\n",
    "        elif c1 < c2:\n",
    "            return s[::2].count('1')\n",
    "        else:\n",
    "            return s[::2].count('0')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        count_0 = s.count('0')\n",
    "        count_1 = len(s) - count_0\n",
    "        \n",
    "        if abs(count_0 - count_1) > 1:\n",
    "            return -1\n",
    "        \n",
    "        target_0 = '01' * (len(s) // 2) + '0'\n",
    "        target_1 = '10' * (len(s) // 2) + '1'\n",
    "        \n",
    "        diff_0 = sum(1 for c, t in zip(s, target_0) if c != t)\n",
    "        diff_1 = sum(1 for c, t in zip(s, target_1) if c != t)\n",
    "        \n",
    "        if count_0 > count_1:\n",
    "            return diff_0 // 2\n",
    "        elif count_1 > count_0:\n",
    "            return diff_1 // 2\n",
    "        else:\n",
    "            return min(diff_0 // 2, diff_1 // 2)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        s_list = [int(x) for x in s]\n",
    "        pos = sum(s_list)\n",
    "        neg = len(s_list) - pos\n",
    "        \n",
    "        diff = pos - neg\n",
    "        if len(s_list) < 2:\n",
    "            return 0\n",
    "        if abs(diff) > 1:\n",
    "            return -1\n",
    "        \n",
    "        counter1 = 0\n",
    "        counter2 = 0\n",
    "        for i, item in enumerate(s_list):\n",
    "            if i % 2 == 1 and item:\n",
    "                counter1 += 1\n",
    "            if i % 2 == 0 and item:\n",
    "                counter2 += 1      \n",
    "                     \n",
    "        if diff == 0:\n",
    "            if counter1 == len(s_list) // 2 or counter1 == 0:\n",
    "                return 0\n",
    "            return len(s_list) // 2 - max(counter1, counter2)\n",
    "\n",
    "        if diff > 0:\n",
    "            if not counter1:\n",
    "                return 0\n",
    "            return len(s_list) // 2 - counter2 + 1\n",
    "        else:\n",
    "            if not counter2:\n",
    "                return 0\n",
    "            return len(s_list) // 2 - counter1\n",
    "                    \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        cnt = [0, 0]    # 第一位表示开头为1时不同的数量，第二位表示开头为0时不同的数量\n",
    "        c1 = 0\n",
    "        for i, c in enumerate(s):\n",
    "            # 偶数为1，给1加，偶数为0，给0加。奇数为1，给0加，奇数为0，给1加\n",
    "            cnt[i & 1 ^ int(c)] += 1\n",
    "            if c == '1':\n",
    "                c1 += 1\n",
    "\n",
    "        c0 = len(s) - c1\n",
    "        if abs(c1 - c0) > 1:\n",
    "            return -1\n",
    "        if c1 > c0:\n",
    "            diff = cnt[0]\n",
    "        elif c1 == c0:\n",
    "            diff = min(cnt)\n",
    "        else:\n",
    "            diff = cnt[1]\n",
    "        return diff + 1 >> 1\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        diff = s.count('1')-s.count('0')\n",
    "        if diff>1 or diff <-1:\n",
    "            return -1\n",
    "        ans1 = len(s)\n",
    "        ans2 = len(s)\n",
    "        if diff >= 0 :\n",
    "            ans1 = sum([0 if i % 2==0 and s[i]==\"1\" or i % 2 == 1 and s[i]==\"0\" else 1 for i in range(len(s))])//2\n",
    "        if diff <= 0:\n",
    "            ans2 = sum([0 if i % 2==0 and s[i]==\"0\" or i % 2 == 1 and s[i]==\"1\" else 1 for i in range(len(s))])//2\n",
    "        \n",
    "        \n",
    "        return min(ans1,ans2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "\n",
    "        if abs(s.count('1') - s.count('0')) > 1:\n",
    "            return -1\n",
    "\n",
    "        ls = list(s)\n",
    "        n = len(ls)\n",
    "        if n % 2 == 0:\n",
    "            cnt1 = ls[1::2].count('1')\n",
    "            cnt2 = ls[::2].count('1')\n",
    "            res = min(int(n / 2) - cnt1, int(n / 2) - cnt2)\n",
    "        else:\n",
    "            if ls.count('1') > ls.count('0'):\n",
    "                res = int(n / 2) + 1 - ls[::2].count('1')\n",
    "            else:\n",
    "                res = int(n / 2) + 1 - ls[::2].count('0')\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        zero,one = 0,0\n",
    "        for ch in s:\n",
    "            if ch=='0':\n",
    "                zero += 1\n",
    "            else:\n",
    "                one += 1\n",
    "\n",
    "        if abs(zero-one)>1:\n",
    "            return -1\n",
    "\n",
    "        res1,res2 = 0,0\n",
    "        # 101010..\n",
    "        for i in range(len(s)):\n",
    "            if i%2==0 and s[i]!='1':\n",
    "                res1 += 1\n",
    "            elif i%2==1 and s[i]!='0':\n",
    "                res1 += 1\n",
    "\n",
    "        if zero+1==one:\n",
    "            return res1//2\n",
    "                \n",
    "\n",
    "        # 010101..\n",
    "        for i in range(len(s)):\n",
    "            if i%2==0 and s[i]!='0':\n",
    "                res2 += 1\n",
    "            elif i%2==1 and s[i]!='1':\n",
    "                res2 += 1\n",
    "\n",
    "        if one+1==zero:\n",
    "            return res2//2\n",
    "\n",
    "        \n",
    "        return min(res1,res2)//2\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        cnt_0 = s.count('0')\n",
    "        cnt_1 = s.count('1')\n",
    "        def check(x):\n",
    "            cnt = 0\n",
    "            for y in s[::2]:\n",
    "                cnt += int(y) ^ x\n",
    "            return cnt\n",
    "        if cnt_1 == 1 + cnt_0:\n",
    "            return check(1)\n",
    "        elif cnt_1 + 1 == cnt_0:\n",
    "            return check(0)\n",
    "        elif cnt_1 == cnt_0:\n",
    "            return min(check(0), check(1))\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        cnt = [0, 0]    # 第一位表示开头为1时不同的数量，第二位表示开头为0时不同的数量\n",
    "        c1 = 0\n",
    "        for i, c in enumerate(s):\n",
    "            # 偶数为1，给1加，偶数为0，给0加。奇数为1，给0加，奇数为0，给1加\n",
    "            cnt[i & 1 ^ int(c)] += 1\n",
    "            if c == '1':\n",
    "                c1 += 1\n",
    "\n",
    "        c0 = len(s) - c1\n",
    "        if abs(c1 - c0) > 1:\n",
    "            return -1\n",
    "        if c1 > c0:\n",
    "            diff = cnt[0]\n",
    "        elif c1 == c0:\n",
    "            diff = min(cnt)\n",
    "        else:\n",
    "            diff = cnt[1]\n",
    "        return diff + 1 >> 1\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        n=len(s)\n",
    "        c0=s.count('0')\n",
    "        c1=n-c0\n",
    "        if n%2==1:\n",
    "            if abs(c0-c1)!=1:\n",
    "                return -1\n",
    "            if c1>c0:\n",
    "                s1 = '1'+'01'*(n//2)\n",
    "            else:\n",
    "                s1 = '0'+'10'*(n//2)\n",
    "            return sum(1 for c1,c2 in zip(s, s1) if c1!=c2) // 2\n",
    "        # n is even\n",
    "        if c0!=c1:\n",
    "            return -1\n",
    "        s1='01'*(n//2)\n",
    "        d1 = sum(1 for c1,c2 in zip(s, s1) if c1!=c2)\n",
    "        return min(d1, n-d1) // 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        cnt_0 = s.count('0')\n",
    "        cnt_1 = s.count('1')\n",
    "        if abs(cnt_0 - cnt_1) > 1: return -1\n",
    "        def check(s):\n",
    "            start = s[0]\n",
    "            cnt = 0\n",
    "            for i in range(0, n, 2):\n",
    "                if i != n-1:\n",
    "                    if s[i] == s[i+1]:\n",
    "                        if s[i] == start:\n",
    "                            cnt += 1\n",
    "                    else:\n",
    "                        if s[i] != start:\n",
    "                            cnt += 1\n",
    "                else:\n",
    "                    if s[i] != start:\n",
    "                        cnt += 1\n",
    "            return cnt\n",
    "        return min(check(s), check(s[::-1]))\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        cnt_0 = s.count('0')\n",
    "        cnt_1 = s.count('1')\n",
    "        if abs(cnt_0 - cnt_1) > 1: return -1\n",
    "        def check(x):\n",
    "            cnt = 0\n",
    "            for i in range(n):\n",
    "                cnt += int(s[i]) ^ x\n",
    "                x ^= 1\n",
    "            return cnt\n",
    "        if cnt_1 > cnt_0:\n",
    "            return check(1) // 2\n",
    "        elif cnt_1 < cnt_0:\n",
    "            return check(0) // 2\n",
    "        return min(check(0), check(1)) // 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        cnt1, cnt2 = 0, 0\n",
    "        print(len(s))\n",
    "        if len(s)%2 == 0:\n",
    "            if Counter(s)['1'] != Counter(s)['0']:\n",
    "                return -1\n",
    "            else:\n",
    "                for i in range(0, len(s)-1, 2):\n",
    "                    if s[i] == '0':\n",
    "                        cnt1 += 1\n",
    "                    else:\n",
    "                        cnt2 += 1\n",
    "                return min(cnt1, cnt2)\n",
    "        if len(s)%2 == 1:\n",
    "            cnt3, cnt4 = 0, 0\n",
    "            if abs(Counter(s)['1'] - Counter(s)['0']) != 1:\n",
    "                return -1\n",
    "            else:\n",
    "                for i in range(0, len(s), 2):\n",
    "                    if s[i] == '0':\n",
    "                        cnt1 += 1\n",
    "                    else:\n",
    "                        cnt2 += 1\n",
    "                for i in range(1, len(s)-1, 2):\n",
    "                    if s[i] == '0':\n",
    "                        cnt3 += 1\n",
    "                    else:\n",
    "                        cnt4 += 1\n",
    "                if cnt1 == cnt4:\n",
    "                    return cnt1\n",
    "                else:\n",
    "                    return cnt2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        n0, n1 = s.count('0'), s.count('1')\n",
    "        res = float(\"INF\")\n",
    "        # \"1010...\"\n",
    "        if n1 == (n + 1) // 2 and n0 == n // 2:   # 不同字符个数相等\n",
    "            diff1 = 0\n",
    "            for i in range(n):\n",
    "                if int(s[i]) == i % 2:   # 对应位数不同\n",
    "                    diff1 += 1\n",
    "            res = min(res, diff1 // 2)\n",
    "        # \"0101...\"\n",
    "        if n0 == (n + 1) // 2 and n1 == n // 2:   # 不同字符个数相等\n",
    "            diff2 = 0\n",
    "            for i in range(n):\n",
    "                if int(s[i]) != i % 2:   # 对应位数不同\n",
    "                    diff2 += 1\n",
    "            res = min(res, diff2 // 2)\n",
    "        if res == float(\"INF\"):\n",
    "            return -1   # 不存在\n",
    "        else:\n",
    "            return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        if abs(s.count('0')-s.count('1'))>1:\n",
    "            return -1\n",
    "        table = [0,1]\n",
    "        n = len(s)\n",
    "        pat = \"\"\n",
    "        for i in range(n):\n",
    "            pat = pat +str(table[i%2])\n",
    "        ans1 = 0\n",
    "        for i in range(n):\n",
    "            if pat[i]!=s[i]:\n",
    "                ans1 += 1\n",
    "        ans1 = ans1//2 if ans1%2==0 else inf\n",
    "        pat = \"\"\n",
    "        for i in range(n):\n",
    "            pat = pat +str(table[(i+1)%2])\n",
    "        ans2 = 0\n",
    "        for i in range(n):\n",
    "            if pat[i]!=s[i]:\n",
    "                ans2 += 1\n",
    "        ans2 = ans2//2 if ans2%2==0 else inf\n",
    "        return min(ans1,ans2) if min(ans1,ans2)!=0 else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        one_even, one_odd = 0 , 0\n",
    "        zero_even, zero_odd = 0, 0\n",
    "        for i, x in enumerate(s):\n",
    "            if x == \"1\":\n",
    "                if i % 2 == 0:\n",
    "                    one_even += 1\n",
    "                else:\n",
    "                    one_odd += 1\n",
    "            else:\n",
    "                if i % 2 == 0:\n",
    "                    zero_even += 1\n",
    "                else:\n",
    "                    zero_odd += 1\n",
    "        if abs(one_even + one_odd - zero_even - zero_odd) > 1:\n",
    "            return -1\n",
    "        elif one_even + one_odd - zero_even - zero_odd == 1:\n",
    "            return one_odd\n",
    "        elif one_even + one_odd - zero_even - zero_odd == -1:\n",
    "            return zero_odd\n",
    "        else:\n",
    "            return min(one_even, one_odd)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        cnt = sum(x=='1' for x in s)\n",
    "        if abs(n-cnt -cnt) >1:\n",
    "            return -1\n",
    "        \n",
    "        def f(s2:str):\n",
    "            nonlocal cnt\n",
    "            d =0 \n",
    "            cnt2 = sum(x=='1' for x in s2)\n",
    "            if cnt2 != cnt:\n",
    "                return inf\n",
    "\n",
    "            for x,y in zip(s,s2):\n",
    "                # print(x,y)\n",
    "                d += (x!=y)\n",
    "            print(d)\n",
    "            return d\n",
    "\n",
    "        return min(f(('01'*n)[:n]),f(('10'*n)[:n]))//2\n",
    "         \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        cnt = [0, 0]    # 第一位表示开头为1时不同的数量，第二位表示开头为0时不同的数量\n",
    "        c1 = 0\n",
    "        for i, c in enumerate(s):\n",
    "            # 偶数为1，给1加;偶数为0，给0加\n",
    "            # 奇数为1，给0加;奇数为0，给1加\n",
    "            cnt[i & 1 ^ (c == '1')] += 1\n",
    "            if c == '1':\n",
    "                c1 += 1\n",
    "\n",
    "        c0 = len(s) - c1\n",
    "        if abs(c1 - c0) > 1:\n",
    "            return -1\n",
    "        if c1 > c0:\n",
    "            diff = cnt[0]\n",
    "        elif c1 == c0:\n",
    "            diff = min(cnt)\n",
    "        else:\n",
    "            diff = cnt[1]\n",
    "        return diff + 1 >> 1\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        cnt0, cnt1 = s.count('0'), s.count('1')\n",
    "        n = len(s)\n",
    "        if not ((n % 2 and abs(cnt0 - cnt1) == 1) or (n % 2 == 0 and cnt0 == cnt1)):\n",
    "            return -1 \n",
    "        \n",
    "        \n",
    "        t1 = '01' * (n // 2)\n",
    "        t2 = '10' * (n // 2)\n",
    "        if n % 2:\n",
    "            t1 += '0'\n",
    "            t2 += '1'\n",
    "        ans = n\n",
    "        c1 = sum(a != b for a, b in zip(s, t1))\n",
    "        if c1 % 2 == 0: ans = min(ans, c1 // 2)\n",
    "        c2 = sum(a != b for a, b in zip(s, t2))\n",
    "        if c2 % 2 == 0: ans = min(ans, c2 // 2)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        cnt = [0, 0]    # 第一位表示开头为1时不同的数量，第二位表示开头为0时不同的数量\n",
    "        c1 = 0\n",
    "        for i, c in enumerate(s):\n",
    "            # 偶数为1，给1加;偶数为0，给0加\n",
    "            # 奇数为1，给0加;奇数为0，给1加\n",
    "            cnt[i & 1 ^ int(c)] += 1\n",
    "            if c == '1':\n",
    "                c1 += 1\n",
    "\n",
    "        c0 = len(s) - c1\n",
    "        if abs(c1 - c0) > 1:\n",
    "            return -1\n",
    "\n",
    "        if c1 > c0:\n",
    "            diff = cnt[0]\n",
    "        elif c1 == c0:\n",
    "            diff = min(cnt)\n",
    "        else:\n",
    "            diff = cnt[1]\n",
    "        return diff + 1 >> 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        one_cnt = s.count('1')\n",
    "        if abs(one_cnt - (n - one_cnt)) >= 2:\n",
    "            return -1\n",
    "\n",
    "        # 奇数 1\n",
    "        one_cnt1, zero_cnt1 = 0, 0\n",
    "        for i in range(n):\n",
    "            if i % 2 == 0 and s[i] != '0':\n",
    "                zero_cnt1 += 1\n",
    "            if i % 2 and s[i] != '1':\n",
    "                one_cnt1 += 1\n",
    "        cnt1 = one_cnt1 if one_cnt1 == zero_cnt1 else inf\n",
    "        # 偶数1\n",
    "        one_cnt2, zero_cnt2 = 0, 0\n",
    "        for i in range(n):\n",
    "            if i % 2 == 0 and s[i] != '1':\n",
    "                one_cnt2 += 1\n",
    "            if i % 2 and s[i] != '0':\n",
    "                zero_cnt2 += 1\n",
    "        cnt2 = one_cnt2 if one_cnt2 == zero_cnt2 else inf\n",
    "        return min(cnt1, cnt2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        import math\n",
    "        num1 = s.count('1')\n",
    "        num0 = s.count('0')\n",
    "        if abs(num1 - num0) > 1:\n",
    "            return -1\n",
    "        n = len(s)\n",
    "        valid_s = []\n",
    "        if n % 2 == 0:\n",
    "            valid_s.append('10' * num0)\n",
    "            valid_s.append('01' * num0)\n",
    "        else:\n",
    "            if num1 > num0:\n",
    "                valid_s.append('10' * num0 + '1')\n",
    "            else:\n",
    "                valid_s.append('01' * num0 + '0')\n",
    "        ans = math.inf\n",
    "        # print(valid_s)\n",
    "        for val_s in valid_s:\n",
    "            cnt = sum(val_s[i] != s[i] for i in range(n))\n",
    "            ans = min(ans, cnt//2)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        cnt0 = s.count('0')\n",
    "        cnt1 = n - cnt0\n",
    "        if abs(cnt0 - cnt1) > 1:\n",
    "            return -1\n",
    "        c1 = '0'\n",
    "        c2 = '1'\n",
    "        k1 = k2 = 0\n",
    "        if n % 2:\n",
    "            if cnt1 > cnt0:\n",
    "                c1 = '1'\n",
    "                c2 = '0'\n",
    "            for i in range(0, n, 2):\n",
    "                if i == n - 1:\n",
    "                    k1 += (s[i] != c1)\n",
    "                else:\n",
    "                    k1 += (s[i] != c1) + (s[i + 1] != c2)\n",
    "            return k1 // 2\n",
    "        else:\n",
    "            for i in range(0, n, 2):\n",
    "                k1 += (s[i] != c1) + (s[i + 1] != c2)\n",
    "                k2 += (s[i] != c2) + (s[i + 1] != c1)\n",
    "            return min(k1 // 2, k2 // 2)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        num0, num1 = 0, 0\n",
    "        for c in s:\n",
    "            if c == '0':\n",
    "                num0 += 1\n",
    "            else:\n",
    "                num1 += 1\n",
    "        if abs(num0 - num1) > 1:\n",
    "            return -1\n",
    "        ans = 0\n",
    "        n = len(s)\n",
    "        if num1 > num0:\n",
    "            for i in range(0, n, 2):\n",
    "                    if s[i] != '1':\n",
    "                        ans += 1\n",
    "        elif num0 > num1:\n",
    "            for i in range(0, n, 2):\n",
    "                if s[i] != '0':\n",
    "                    ans += 1\n",
    "        else:\n",
    "            for i in range(0, n, 2):\n",
    "                    if s[i] != '1':\n",
    "                        ans += 1\n",
    "            tmp = 0\n",
    "            for i in range(0, n, 2):\n",
    "                if s[i] != '0':\n",
    "                    tmp += 1\n",
    "            ans = min(ans, tmp)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        num0=0\n",
    "        num1=0\n",
    "        for s0 in s:\n",
    "            if s0==\"1\":\n",
    "                num1+=1\n",
    "            else:\n",
    "                num0+=1\n",
    "        n=len(s)\n",
    "        print(num0,num1)\n",
    "        if n%2==0:\n",
    "            if num0!=num1:\n",
    "                return -1\n",
    "        if n%2==1:\n",
    "            if abs(num0-num1)>1:\n",
    "                return -1\n",
    "        cnt=0\n",
    "        cnt1=0\n",
    "        for i in range(0,n,2):\n",
    "                if s[i]!=\"1\":\n",
    "                    cnt+=1\n",
    "        for i in range(1,n,2):\n",
    "            if s[i]!=\"1\":\n",
    "                cnt1+=1\n",
    "        if num0==num1:\n",
    "            return min(cnt1,cnt)\n",
    "        if num0>num1:\n",
    "            return cnt1\n",
    "        else:\n",
    "            return cnt\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution():\n",
    "\tdef minSwaps(self, s: str) -> int:\n",
    "\t\tz=o=0\n",
    "\t\tfor c in s:\n",
    "\t\t\tif c==\"0\":\n",
    "\t\t\t\tz+=1\n",
    "\t\t\telse:\n",
    "\t\t\t\to+=1\n",
    "\t\tif abs(z-o)>1:\n",
    "\t\t\treturn -1\n",
    "\t\tif z>o:\n",
    "\t\t\tcur=0\n",
    "\t\telse:\n",
    "\t\t\tcur=1\n",
    "\t\tw=0\n",
    "\t\tfor c in s:\n",
    "\t\t\tif int(c) != cur:\n",
    "\t\t\t\tw+=1\n",
    "\t\t\tcur=abs(cur-1)\n",
    "\t\tif z==o:\n",
    "\t\t\tcur=0\n",
    "\t\t\tw2=0\n",
    "\t\t\tfor c in s:\n",
    "\t\t\t\tif int(c) != cur:\n",
    "\t\t\t\t\tw2+=1\n",
    "\t\t\t\tcur=abs(cur-1)\n",
    "\t\t\treturn min(w//2,w2//2)\n",
    "\t\treturn w//2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        # 如果1个数比0个数多1，那么目标是101010，如果0比1多1，目标是01010，不同位数//2\n",
    "        # 如果0和1个数相同，那么需要考虑哪种情况操作少\n",
    "        cnt1,cnt0=s.count('1'),s.count('0')\n",
    "        if cnt1+1==cnt0:\n",
    "            cnt=0\n",
    "            for i,c in enumerate(s):\n",
    "                if i%2==0 and c=='1':\n",
    "                    cnt+=1\n",
    "                elif i%2==1 and c=='0':\n",
    "                    cnt+=1\n",
    "            return cnt//2\n",
    "        elif cnt1-1==cnt0:\n",
    "            cnt=0\n",
    "            for i,c in enumerate(s):\n",
    "                if i%2==0 and c=='0':\n",
    "                    cnt+=1\n",
    "                elif i%2==1 and c=='1':\n",
    "                    cnt+=1\n",
    "            return cnt//2\n",
    "        elif cnt0==cnt1:\n",
    "            ans=inf\n",
    "            c1,c2=0,0\n",
    "            for i,c in enumerate(s):\n",
    "                if i%2==0 and c=='0':\n",
    "                    c1+=1\n",
    "                elif i%2==1 and c=='1':\n",
    "                    c1+=1\n",
    "                elif i%2==0 and c=='1':\n",
    "                    c2+=1\n",
    "                elif i%2==1 and c=='0':\n",
    "                    c2+=1\n",
    "            # print(c1,c2,ans)\n",
    "            ans=min(ans,c1//2,c2//2)\n",
    "            return ans \n",
    "        else:\n",
    "            return -1\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        a = b = 0\n",
    "        c = d = 0\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == str(i%2):\n",
    "                b += 1\n",
    "            else:\n",
    "                a += 1\n",
    "            if s[i] == '0':\n",
    "                c += 1\n",
    "            else:\n",
    "                d += 1\n",
    "                \n",
    "\n",
    "        \n",
    "        if max(c, d) - min(c, d) > 1:\n",
    "            return -1\n",
    "            \n",
    "        if a % 2 == 1 and b % 2 == 1:\n",
    "            return -1\n",
    "        \n",
    "        if a % 2 == 1:\n",
    "            return b//2\n",
    "        \n",
    "        if b % 2 == 1:\n",
    "            return a//2\n",
    "\n",
    "        \n",
    "       \n",
    "\n",
    "        return min(a//2, b//2)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        cnt_0 = s.count('0')\n",
    "        cnt_1 = s.count('1')\n",
    "        tmp = list(map(int, s))\n",
    "        def check(x):\n",
    "            cnt = 0\n",
    "            for y in tmp[::2]:\n",
    "                cnt += y ^ x\n",
    "            return cnt\n",
    "        if cnt_1 == 1 + cnt_0:\n",
    "            return check(1)\n",
    "        elif cnt_1 + 1 == cnt_0:\n",
    "            return check(0)\n",
    "        elif cnt_1 == cnt_0:\n",
    "            return min(check(0), check(1))\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        ans = n\n",
    "        cnt_0, cnt_1 = s.count('0'), s.count('1')\n",
    "        if abs(cnt_0 - cnt_1) > 1: return -1\n",
    "        if cnt_0 == cnt_1:\n",
    "            tmp1, tmp2 = '0', '1'\n",
    "            cnt1, cnt2 = 0, 1\n",
    "            for i in range(1, n):\n",
    "                tmp1 += str(1 - cnt1)\n",
    "                tmp2 += str(1 - cnt2)\n",
    "                cnt1, cnt2 = 1 - cnt1, 1 - cnt2\n",
    "            cnt = 0\n",
    "            for x, y in zip(s, tmp1):\n",
    "                if x != y: cnt += 1\n",
    "\n",
    "            ans = min(ans, cnt // 2)\n",
    "            cnt = 0\n",
    "            for x, y in zip(s, tmp2):\n",
    "                if x != y: cnt += 1\n",
    "\n",
    "            ans = min(ans, cnt // 2)\n",
    "        elif cnt_0 > cnt_1:\n",
    "            tmp1 = '0'\n",
    "            cnt1 = 0\n",
    "            for i in range(1, n):\n",
    "                tmp1 += str(1 - cnt1)\n",
    "                cnt1 = 1 - cnt1\n",
    "            cnt = 0\n",
    "            for x, y in zip(s, tmp1):\n",
    "                if x != y: cnt += 1\n",
    "\n",
    "            ans = min(ans, cnt // 2)\n",
    "        else:\n",
    "            tmp1 = '1'\n",
    "            cnt1 = 1\n",
    "            for i in range(1, n):\n",
    "                tmp1 += str(1 - cnt1)\n",
    "                cnt1 = 1 - cnt1\n",
    "            cnt = 0\n",
    "            for x, y in zip(s, tmp1):\n",
    "                if x != y: cnt += 1\n",
    "                \n",
    "            ans = min(ans, cnt // 2)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        num0 = 0\n",
    "        num1 = 0\n",
    "        for ch in s:\n",
    "            if ch == '1':\n",
    "                num1 += 1\n",
    "            else:\n",
    "                num0 += 1\n",
    "        if int(abs(num0 - num1)) > 1:\n",
    "            return -1\n",
    "        odd0 = 0\n",
    "        odd1 = 0\n",
    "        for i in range(len(s)):\n",
    "            if i % 2 != 0:\n",
    "                if s[i] == '0':\n",
    "                    odd0 += 1\n",
    "                else:\n",
    "                    odd1 += 1\n",
    "        if len(s) % 2 == 0:\n",
    "            return min(odd0, odd1)\n",
    "        else:\n",
    "            if num0 > num1:\n",
    "                return odd0\n",
    "            else:\n",
    "                return odd1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        ans = inf\n",
    "        diff = 0\n",
    "        n0, n1 = s.count('0'), s.count('1')\n",
    "        if n0 == (n + 1) // 2 and n1 == n // 2:\n",
    "            for i in range(n):\n",
    "                if int(s[i]) != i % 2:\n",
    "                    diff += 1\n",
    "            ans = min(ans, diff // 2)\n",
    "        diff = 0\n",
    "        if n1 == (n + 1) // 2 and n0 == n // 2:\n",
    "            for i in range(n):\n",
    "                if int(s[i]) == i % 2:\n",
    "                    diff += 1\n",
    "            ans = min(ans, diff // 2)\n",
    "        return ans if ans != inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        cnt0 = s.count('0')\n",
    "        cnt1 = len(s) - cnt0\n",
    "        delta = abs(cnt0 - cnt1)\n",
    "        ans = 0\n",
    "        res = 0\n",
    "        if delta >= 2:\n",
    "            return -1\n",
    "        else:\n",
    "            for i in range(0, len(s), 2):\n",
    "                if s[i] == '1':\n",
    "                    ans += 1\n",
    "                else:\n",
    "                    res += 1\n",
    "            if cnt0 > cnt1:\n",
    "                return ans\n",
    "            elif cnt0 == cnt1:\n",
    "                return min(ans, res)\n",
    "            else:\n",
    "                return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        one_cnt = s.count('1')\n",
    "        if abs(one_cnt - (n - one_cnt)) >= 2:\n",
    "            return -1\n",
    "        # 10101\n",
    "        zero_cnt1, one_cnt1 = 0, 0\n",
    "        for i in range(n):\n",
    "            if not i % 2 and s[i] != '1':\n",
    "                zero_cnt1 += 1\n",
    "            if i % 2 and s[i] != '0':\n",
    "                one_cnt1 += 1\n",
    "        cnt1 = one_cnt1 if one_cnt1 == zero_cnt1 else inf\n",
    "        # 01010\n",
    "        zero_cnt2, one_cnt2 = 0, 0\n",
    "        for i in range(n):\n",
    "            if not i % 2 and s[i] != '0':\n",
    "                one_cnt2 += 1\n",
    "            if i % 2 and s[i] != '1':\n",
    "                zero_cnt2 += 1\n",
    "        cnt2 = one_cnt2 if one_cnt2 == zero_cnt2 else inf\n",
    "        return min(cnt1, cnt2)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        cnt_0 = s.count('0')\n",
    "        cnt_1 = s.count('1')\n",
    "        if abs(cnt_0 - cnt_1) > 1: return -1\n",
    "        def check(s):\n",
    "            start = s[0]\n",
    "            cnt = 0\n",
    "            for i in range(0, n, 2):\n",
    "                if i != n-1:\n",
    "                    if s[i] == s[i+1]:\n",
    "                        if s[i] == start:\n",
    "                            cnt += 1\n",
    "                    else:\n",
    "                        if s[i] != start:\n",
    "                            cnt += 1\n",
    "                else:\n",
    "                    if s[i] != start:\n",
    "                        cnt += 1\n",
    "            return cnt\n",
    "        return min(check(s), check(s[::-1]))\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        cnt_0 = s.count('0')\n",
    "        cnt_1 = n - cnt_0\n",
    "        if abs(cnt_0 - cnt_1) > 1: return -1\n",
    "        tmp = list(map(int, s))\n",
    "        def check(x):\n",
    "            cnt = 0\n",
    "            for i in range(n):\n",
    "                cnt += tmp[i] ^ x\n",
    "                x ^= 1\n",
    "            return cnt\n",
    "        if cnt_1 > cnt_0:\n",
    "            return check(1) // 2\n",
    "        elif cnt_1 < cnt_0:\n",
    "            return check(0) // 2\n",
    "        return min(check(0), check(1)) // 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        c = Counter(s)\n",
    "        if abs(c['0'] - c['1']) > 1: return -1\n",
    "        if len(s) % 2 == 0:\n",
    "            res = sum([1 if (i % 2 == 0 and s[i] == '0') else 0 for i in range(len(s))])\n",
    "            return min(res, len(s) // 2 - res)\n",
    "        else:\n",
    "            key = '0' if c['0'] > c['1'] else '1'\n",
    "            res = sum([1 if (i % 2 == 0 and s[i] != key) else 0 for i in range(len(s))])\n",
    "            return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        left = 0\n",
    "        diff = 0\n",
    "        for c in s:\n",
    "            if c == '[':\n",
    "                left += 1\n",
    "            elif left > 0:\n",
    "                left -= 1\n",
    "            else:\n",
    "                diff += 1\n",
    "        return diff + 1 >> 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        ret = 0\n",
    "        left = 0\n",
    "        for x in s:\n",
    "            if x == '[':\n",
    "                left += 1\n",
    "            else:\n",
    "                if left == 0:\n",
    "                    ret += 1\n",
    "                    left = 1\n",
    "                else:\n",
    "                    left -= 1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        ans = 0\n",
    "        count = 0\n",
    "        for per in s:\n",
    "            if per == \"[\":\n",
    "                count += 1\n",
    "            elif per == ']' and count > 0:\n",
    "                count -= 1\n",
    "            elif per == ']' and count == 0:\n",
    "                ans += 1\n",
    "                count += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        res = 0\n",
    "        cnt = 0\n",
    "        for c in s:\n",
    "            if c == '[':\n",
    "                cnt += 1\n",
    "            else:\n",
    "                cnt -= 1\n",
    "            if cnt < 0:\n",
    "                res += 1\n",
    "                cnt += 2\n",
    "                \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        left, right = 0, 0\n",
    "        ans = 0\n",
    "        i, j = 0, len(s) - 1\n",
    "        while i < j:\n",
    "            if left != -1:\n",
    "                left += 1 if s[i] == '[' else -1\n",
    "                if left != -1:\n",
    "                    i += 1\n",
    "            if right != 1:\n",
    "                right += 1 if s[j] == '[' else -1\n",
    "                if right != 1:\n",
    "                    j -= 1\n",
    "            if left == -1 and right == 1:\n",
    "                ans += 1\n",
    "                left, right = 1, -1\n",
    "                i += 1\n",
    "                j -= 1\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        balance = 0\n",
    "        max_imbalance = 0\n",
    "        for c in s:\n",
    "            if c == \"[\":\n",
    "                balance += 1\n",
    "            elif c == \"]\":\n",
    "                balance -= 1\n",
    "\n",
    "            max_imbalance = min(max_imbalance, balance)\n",
    "        return (-max_imbalance+1) // 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        counts=[0,0]\n",
    "        extra=0\n",
    "        for i in range(0,len(s)):\n",
    "            if s[i]=='[':\n",
    "                counts[0]+=1\n",
    "            else:\n",
    "                if counts[1]==counts[0]:\n",
    "                    extra+=1\n",
    "                else:\n",
    "                    counts[1]+=1\n",
    "        return (extra+1)>>1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "\n",
    "        res = 0\n",
    "        cnt = 0\n",
    "        for c in s:\n",
    "            if c == '[':\n",
    "                cnt += 1\n",
    "            else:\n",
    "                cnt -= 1\n",
    "            if cnt < 0:\n",
    "                res += 1\n",
    "                cnt += 2\n",
    "        \n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minSwaps(self, s: str) -> int:\r\n",
    "        lf = 0\r\n",
    "        rt = 0\r\n",
    "        for c in s:\r\n",
    "            if c == '[':\r\n",
    "                lf += 1\r\n",
    "            else:\r\n",
    "                if lf > 0:\r\n",
    "                    lf -= 1\r\n",
    "                else:\r\n",
    "                    rt += 1\r\n",
    "        return (lf + 1) // 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        now,ret=0,0\n",
    "        for ch in s:\n",
    "            if ch==\"[\":\n",
    "                now+=1\n",
    "            else:\n",
    "                now-=1\n",
    "                if now<0:\n",
    "                    now=1\n",
    "                    ret+=1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        ans,r=0,0\n",
    "        for i in s:\n",
    "            if i=='[':\n",
    "                r+=1\n",
    "            elif r==0:\n",
    "                ans+=1\n",
    "            else:\n",
    "                r-=1\n",
    "        return (ans+1)//2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "\n",
    "        # 恰好 由 n / 2 个,b 那就不用考虑不匹配情况\n",
    "        '''\n",
    "        分析：贪心。\n",
    "        对于括号序列，排除掉能够匹配的[]之后，剩余的串有什么特点呢？其实，剩余的串是]]]....[[[这种格式，即左边全是左括号，右边全是右括号。\n",
    "\n",
    "        根据数学归纳法，]]]....[[[这种情况交换的次数是：左括号的数量 ÷ 2 向上取整。\n",
    "        交换的是：最左边的】和最右边的【，可能会形成1/组个匹配的，所以是除以2 看情况+1，向上取整\n",
    "        比如]]][[[，左括号的数量为3，需要交换的最小次数为(3 + 1) / 2 = 2；\n",
    "        再比如][，左括号的数量为1，需要交换的次数为(1 + 1) / 2 = 1 ；\n",
    "        当然，这里左括号的数量 = 右括号的数量。\n",
    "\n",
    "        下面的代码中：变量l从左向右统计左括号的数量，与此同时，变量unmatched统计右括号的数量，如果配对的话，让l--；如果不配对的话，让unmatched++；\n",
    "        最终unmatched中存的是剩余右括号的数量 ==亦等于剩余左括号的数量。\n",
    "        答案就是 (unmatched + 1) / 2;\n",
    "\n",
    "        时间复杂度 O(n):遍历一遍字符串\n",
    "        '''\n",
    "        l, unmatched =0, 0\n",
    "        # unmatchedes=0\n",
    "\n",
    "        for c in s:\n",
    "          if c == '[':\n",
    "            l += 1\n",
    "          else:\n",
    "            if l > 0:\n",
    "              l -= 1\n",
    "            \n",
    "            else:\n",
    "              # 不配出现，\n",
    "              unmatched += 1\n",
    "\n",
    "        return (unmatched + 1)//2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        r = len(s) - 1\n",
    "        while s[r] != '[':\n",
    "            r -= 1\n",
    "\n",
    "        cnt = 0\n",
    "        l = 0\n",
    "        res = 0\n",
    "        while l < r:\n",
    "            if s[l] == '[':\n",
    "                cnt += 1\n",
    "            elif cnt > 0:\n",
    "                cnt -= 1\n",
    "            else:\n",
    "                res += 1\n",
    "                cnt += 1\n",
    "                r -= 1\n",
    "                while r > l and s[r] != '[':\n",
    "                    r -= 1\n",
    "        \n",
    "            l += 1\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        res = cnt = 0\n",
    "        for ch in s:\n",
    "            if ch == '[':\n",
    "                cnt += 1\n",
    "            else:\n",
    "                cnt -= 1\n",
    "            if cnt < 0:\n",
    "                res += 1\n",
    "                cnt += 2\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        res = 0\n",
    "        cnt = 0\n",
    "        for c in s:\n",
    "            if c == '[':\n",
    "                cnt += 1\n",
    "            else:\n",
    "                cnt -= 1\n",
    "            if cnt < 0:\n",
    "                res += 1\n",
    "                cnt += 2\n",
    "                \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        n=s.count(\"[\")*2\n",
    "        c=0\n",
    "        s1,s2=0,0\n",
    "        for i in range(n):\n",
    "            if s[i]==\"[\":\n",
    "                s1+=1\n",
    "            else:\n",
    "                s2+=1\n",
    "            if s1<s2:\n",
    "                s1+=1\n",
    "                s2-=1\n",
    "                c+=1\n",
    "        return c\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def minSwaps(self, s: str) -> int:\n",
    "        c = 0\n",
    "        for i in s:\n",
    "            if i == ']' and c > 0:\n",
    "                c -= 1\n",
    "            else:\n",
    "                c += 1\n",
    "        return c//2\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        ans = 0\n",
    "        l, r = 0, 0\n",
    "        for c in s:\n",
    "            if c=='[':\n",
    "                l += 1\n",
    "            else:\n",
    "                r += 1\n",
    "            if r>l:\n",
    "                ans += 1\n",
    "                r -= 1\n",
    "                l += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        n=s.count(\"[\")*2\n",
    "        c=0\n",
    "        s1,s2=0,0\n",
    "        for i in range(n):\n",
    "            if s[i]==\"[\":\n",
    "                s1+=1\n",
    "            else:\n",
    "                s2+=1\n",
    "            if s1<s2:\n",
    "                #s[i]=\"[\"\n",
    "                s1+=1\n",
    "                s2-=1\n",
    "                c+=1\n",
    "        return c\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        left_cnt = 0\n",
    "        for i in s:\n",
    "            if i == '[':\n",
    "                left_cnt += 1\n",
    "            else:\n",
    "                left_cnt = max( 0 , left_cnt - 1 )\n",
    "        return ceil(left_cnt/2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        ans = count = 0\n",
    "        for c in s:\n",
    "            if c == '[': count += 1\n",
    "            else:\n",
    "                if not count:\n",
    "                    # 将最右的'['和这个']'互换，后面的count会多1\n",
    "                    # 由于数量相等，不影响再往后的右括号\n",
    "                    ans += 1\n",
    "                    count += 1\n",
    "                else:\n",
    "                    count -= 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        #直接贪心\n",
    "        right, left = 0, 0\n",
    "        for c in s:\n",
    "            if c == ']':\n",
    "                if left > 0:\n",
    "                    left -= 1\n",
    "                else:\n",
    "                    right += 1\n",
    "            if c == '[':\n",
    "                left += 1\n",
    "        \n",
    "        if right % 2 == 0:\n",
    "            return right // 2\n",
    "        else:\n",
    "            return (right // 2) + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        n=s.count(\"[\")*2\n",
    "        c=0\n",
    "        s1,s2=0,0\n",
    "        for i in range(n):\n",
    "            if s[i]==\"[\":\n",
    "                s1+=1\n",
    "            else:\n",
    "                s2+=1\n",
    "            if s1<s2:\n",
    "                s1+=1\n",
    "                s2-=1\n",
    "                c+=1\n",
    "        return c\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        l = 0\n",
    "        r = 0\n",
    "        swap = 0\n",
    "\n",
    "        for c in s:\n",
    "            if c == '[':\n",
    "                l += 1\n",
    "            else:\n",
    "                r += 1\n",
    "            \n",
    "            if r > l:\n",
    "                swap += 1\n",
    "                r -= 1\n",
    "                l += 1\n",
    "        \n",
    "        return swap"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        cnt = 0\n",
    "        mx = 0\n",
    "        for c in s:\n",
    "            if c == ']':\n",
    "                cnt += 1\n",
    "                if cnt > mx:\n",
    "                    mx = cnt\n",
    "            else:\n",
    "                cnt -= 1\n",
    "        return mx + 1 >> 1\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        extra_close, max_close = 0, 0\n",
    "        for c in s:\n",
    "            if c == '[':\n",
    "                extra_close -= 1\n",
    "            else:\n",
    "                extra_close += 1\n",
    "            max_close = max(extra_close, max_close)\n",
    "        return (max_close + 1) // 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        res = 0\n",
    "        cnt = 0\n",
    "        for c in s:\n",
    "            if c == '[':\n",
    "                cnt += 1\n",
    "            else:\n",
    "                cnt -= 1\n",
    "            if cnt < 0:\n",
    "                res += 1\n",
    "                cnt += 2\n",
    "                \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        cnt = mincnt = 0\n",
    "        for ch in s:\n",
    "            if ch == '[':\n",
    "                cnt += 1\n",
    "            else:\n",
    "                cnt -= 1\n",
    "                mincnt = min(mincnt, cnt)\n",
    "        return (-mincnt + 1) // 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        ans, cnt = 0, 0\n",
    "        for c in s:\n",
    "            if c == '[':\n",
    "                cnt+=1\n",
    "            elif cnt > 0:\n",
    "                cnt-=1\n",
    "            else:\n",
    "                cnt+=1\n",
    "                ans+=1\n",
    "        return ans\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        balance = 0  # 平衡度，初始化为 0\n",
    "        swaps = 0  # 所需的交换次数，初始化为 0\n",
    "        for char in s:\n",
    "            if char == '[':\n",
    "                balance += 1  # 遇到 '['，平衡度加 1\n",
    "            else:\n",
    "                balance -= 1  # 遇到 ']'，平衡度减 1\n",
    "            \n",
    "            # 如果平衡度变为负数，则需要进行一次交换\n",
    "            if balance < 0:\n",
    "                swaps += 1  # 增加交换次数\n",
    "                balance += 2  # 因为交换了一个 '[' 和一个 ']'，平衡度增加 2\n",
    "                \n",
    "        return swaps  # 返回最少交换次数\n",
    "\n",
    "# 测试\n",
    "sol = Solution()\n",
    "print(sol.minSwaps(\"][][\"))  # 输出应为 1\n",
    "print(sol.minSwaps(\"]]][[[\"))  # 输出应为 2\n",
    "print(sol.minSwaps(\"[]\"))  # 输出应为 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        cnt = 0\n",
    "        res = 0\n",
    "        for c in s:\n",
    "            if c == \"[\":\n",
    "                cnt += 1\n",
    "            else:\n",
    "                cnt -= 1\n",
    "                res = min(res, cnt)\n",
    "        return (-res + 1) // 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        ans = 0\n",
    "        c = 0\n",
    "        for a in s:\n",
    "            if a == '[':\n",
    "                c += 1\n",
    "            else:\n",
    "                if c > 0:\n",
    "                    c -= 1\n",
    "                else:\n",
    "                    c += 1\n",
    "                    ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        diff = 0\n",
    "        ans = 0\n",
    "        for ch in s:\n",
    "            if ch == ']':\n",
    "                diff += 1\n",
    "            else:\n",
    "                diff -= 1\n",
    "\n",
    "            if diff > 0:\n",
    "                ans += 1\n",
    "                diff -= 2\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        #直接贪心\n",
    "        right, left = 0, 0\n",
    "        for c in s:\n",
    "            if c == ']':\n",
    "                if left > 0:\n",
    "                    left -= 1\n",
    "                else:\n",
    "                    right += 1\n",
    "            if c == '[':\n",
    "                left += 1\n",
    "        return (right + 1) // 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        ans,r=0,0\n",
    "        for i in s:\n",
    "            if i=='[':\n",
    "                r+=1\n",
    "            elif r==0:\n",
    "                ans+=1\n",
    "                r+=1\n",
    "            else:\n",
    "                r-=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        # cnt表示平衡度\n",
    "        # ]]][[[\n",
    "        # -1 -2 -3 -2 -1 0\n",
    "        # []][[]\n",
    "        # 1 0 -1 0 1 0\n",
    "        # [[][]]\n",
    "        # 答案就是使得最小平衡度变成大于等于0的最小次数，等于-cnt 偶数正好是-cnt//2 ,否则是-cnt+1//2\n",
    "        cnt=0\n",
    "        min_cnt=0\n",
    "        for c in s:\n",
    "            if c=='[':\n",
    "                cnt+=1\n",
    "            else:\n",
    "                cnt-=1\n",
    "                min_cnt=min(min_cnt,cnt)\n",
    "        return (-min_cnt+1)//2 if min_cnt<0 else 0\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        cnt = mincnt = 0\n",
    "        for ch in s:\n",
    "            if ch == '[':\n",
    "                cnt += 1\n",
    "            else:\n",
    "                cnt -= 1\n",
    "                mincnt = min(mincnt, cnt)\n",
    "        return (-mincnt + 1) // 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        ss=[]\n",
    "        e=0\n",
    "        for x in s:\n",
    "            if x==']':\n",
    "                if ss:\n",
    "                   ss.pop()\n",
    "                else:\n",
    "                   e+=1\n",
    "            else:\n",
    "                ss.append('[')   \n",
    "        if e%2:\n",
    "            e=e//2+1\n",
    "        else:\n",
    "            e=e//2    \n",
    "        return e if e else 0                                     \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        \"\"\"\n",
    "        遇到[: 直接入栈\n",
    "        遇到 ] :\n",
    "        栈尾如果是 [, 抵消\n",
    "        如果不是, 变为[ 入栈\n",
    "        交换次数为 栈内剩余符号数量//2\n",
    "        \"\"\"\n",
    "        stk = []\n",
    "        for x in s:\n",
    "            if x == '[':\n",
    "                stk.append(x)\n",
    "            else:\n",
    "                if stk and stk[-1] == '[':\n",
    "                    stk.pop()\n",
    "                else:\n",
    "                    stk.append('[')\n",
    "\n",
    "        return len(stk)//2\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        stack = []\n",
    "        for c in s:\n",
    "            if not stack:\n",
    "                stack.append(c)\n",
    "            else:\n",
    "                if stack[-1] == '[' and c == ']':\n",
    "                    stack.pop()\n",
    "                else:\n",
    "                    stack.append(c)\n",
    "        \n",
    "        k = len(stack) // 2\n",
    "        return (k+1) // 2\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, s: str) -> bool:\n",
    "        if (s == \"\"): # Empty\n",
    "            return True\n",
    "        if (self.isBalanced(s[:(n/2)-1]) and self.isBalanced(s[(n/2)-1:])): # AB\n",
    "            return True\n",
    "        if (s[0] == '[' and s[-1] == ']' and self.isBalanced(s[1:-1])):\n",
    "            return True\n",
    "        \n",
    "        return False # Default\n",
    "\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        ans = 0\n",
    "\n",
    "        if not s:\n",
    "            return ans\n",
    "\n",
    "        stack = []\n",
    "\n",
    "        for c in s:\n",
    "            if c == ']' and stack and stack[-1] == '[':\n",
    "                stack.pop()\n",
    "            else:\n",
    "                stack.append(c)\n",
    "            \n",
    "        return ((len(stack) // 2) + 1) // 2\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        l = []\n",
    "        for i in s:\n",
    "            if i == '[': l.append(0)\n",
    "            if i == ']':\n",
    "                if l and l[-1]==0: l.pop()\n",
    "                else: l.append(1)\n",
    "\n",
    "        return (len(l)//2+1)//2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        ans = 0\n",
    "\n",
    "        if not s:\n",
    "            return ans\n",
    "\n",
    "        stack = []\n",
    "\n",
    "        for c in s:\n",
    "            if c == ']' and stack and stack[-1] == '[':\n",
    "                stack.pop()\n",
    "            else:\n",
    "                stack.append(c)\n",
    "            \n",
    "        return ((len(stack) // 2) + 1) // 2\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        st = []\n",
    "        for c in s:\n",
    "            if not st:\n",
    "                st.append(c)\n",
    "            elif st[-1] == '[' and c == ']':\n",
    "                st.pop()\n",
    "            else:\n",
    "                st.append(c)\n",
    "        if not st:\n",
    "            return 0\n",
    "        n = len(st) // 2\n",
    "        return math.ceil(n / 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        ans = 0\n",
    "        n = len(s)\n",
    "        arr = [s[i] for i in range(n)]\n",
    "        L = []\n",
    "        for i in range(n):\n",
    "            if arr[i] == \"[\":\n",
    "                L.append(arr[i])\n",
    "            elif arr[i] == \"]\":\n",
    "                if len(L)!=0:\n",
    "                    L.pop()\n",
    "                else:\n",
    "                    j = n-1\n",
    "                    while j>i:\n",
    "                        if arr[j] == \"[\":\n",
    "                            arr[i] = ']'\n",
    "                            ans += 1\n",
    "                            break\n",
    "                        j-=1\n",
    "                    L.append(\"[\")\n",
    "        return ans\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
